Sum of Two Integers

发表于

Sum of Two Integers

Question

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example:

Given a = 1 and b = 2, return 3.

Analysis

  • a&b 对于同一位，相同且均为1才会产生进位，故a&b可得进位carry
  • a^b 相当于+操作，同为1产生进位当前位为0，同为0所得为0，不同数字才会得当前位为1的结果
  • 由于进位只能向前进位，故每次对carry进行左移位赋给b，直至b=0

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public int getSum(int a, int b) {
        if(a==0)    return b;
        if(b==0)    return a;
        
        while(b!=0){
            int carry=a&b;
            a=a^b;
            b=carry<<1;
        }
        return a;
    }
}

延伸 Subtraction of Two Number

Analysis

  • 借位

    0-1 需借位 0 1 = 1

    1-1、0-0、1-0均无需借位 0 0 = 0 1 1 = 1 1 0 = 0

    故只有当被减数a当前位数字为0，b当前位为1时才需借位，即borrow=(~a)&b

  • 减法

    0-0=0, 0-1=1, 1-0=1, 1-1=0

    满足异或^, 即 a^=b

  • 第一次a&b所得相当于没考虑借位的减法结果，故只需将b等于borrow左移1位不断减去借位，直至b=0

Code

1
2
3
4
5
6
7
8
9
public int getSubtract(int a, int b) {
	while (b != 0) {
		int borrow = (~a) & b;
		a = a ^ b;
		b = borrow << 1;
	}
	
	return a;
}

延伸 Negative Number

Analysis

Java 如何表示负数

　　任何整数类型都存在负数，那么java中是如何表示负数的呢。

例如 5 在 计算机中的二进制表示为 0101，那么其负数（-5）怎么表示呢？

通过这个步骤就行：

注意，在做如下操作之前，我们应该非常注意5的二进制表示，它的高位一定要为0，也就是说如果5写成101，那么我们必须先将其表示成0101，这样按位取反的时候高位才会变为1。

将5按位取反，标为 1010， 然后加上1，变为1011，即为-5在计算机中的表示。

反过来，看到1011，第一反应看他的高位，如果高位为1，则肯定是个负数，那么他到底是负几呢，如下操作：将1011按位取反，得到0100，然后加上1，则得到其值0101，为5。则说明1011代表的是-5。

将x取反+1，即得其负数

Code

1
2
3
public int negate(int x) {
	return ~x + 1;
}